When you open a padlock icon in your browser, your device and a server that has never met you agree on a shared secret, in public, in a few milliseconds. The agreement rests on a fact so plain a child can state it: multiplying two big prime numbers is easy, and finding which two primes were multiplied is, as far as anyone knows, very hard. Take two primes of a thousand digits each and a laptop multiplies them instantly. Hand someone the product and ask for the pair, and every method we have takes longer than the age of the universe.
That asymmetry is old, pure mathematics. It comes from the oldest corner of the subject, number theory: the study of whole numbers, their divisors and their primes. A graduate's relationship to a number like 1001 changes for life. It is no longer "one thousand and one"; it is 7 × 11 × 13, and that splitting is the number's fingerprint.
Number theory is also the field with the largest gap between how easy a question is to state and how hard it is to answer. This piece builds six ideas you can play with, each with a proof sketch, and ends with the open problems that have outlived everyone who has tried them.
How do you find the biggest number that divides both 1071 and 462? Factoring both works for small numbers. Euclid's method, written around 300 BCE in the Elements and still used in computers today, works for any size and needs no factoring at all. Divide the larger by the smaller and keep the remainder. Then repeat with the smaller number and that remainder, until the remainder is zero. The last non-zero remainder is the answer.
Write a = q·b + r. If d divides both a and b, then d divides r = a − q·b. Conversely, if d divides both b and r, it divides a = q·b + r. The real trick is that the two pairs (a, b) and (b, r) have exactly the same common divisors, so they have the same greatest one. And since the remainder is always smaller than b, the numbers shrink and must hit zero.
Run on 1071 and 462: 1071 = 2·462 + 147, then 462 = 3·147 + 21, then 147 = 7·21 + 0. The answer is 21. Better, running the steps backwards expresses 21 as a combination of the two starting numbers: 21 = 1071·(−3) + 462·7. That identity, Bézout's identity, is the engine of everything later: it is how you find inverses in clock arithmetic and how RSA computes its secret key.
Each row is one division. The last line is Bézout's identity from the extended algorithm. The Fibonacci pair is the worst case for its size: every quotient is 1, so it takes the most steps.
Notice how few steps it takes. For numbers with a thousand digits Euclid's algorithm takes a few thousand steps at most, because the remainder at least halves every two steps. That speed, versus the impossible slowness of factoring, is the first half of the cryptography story.
A prime is a whole number greater than 1 whose only divisors are 1 and itself: 2, 3, 5, 7, 11, 13, …. Every other number above 1 is a product of primes. A natural question: does the list ever stop?
Suppose there were only finitely many primes, say p₁, p₂, …, pk. Multiply them all and add one: N = p₁p₂⋯pk + 1. N has some prime factor, because every number above 1 does. That factor cannot be any pi, because dividing N by pi leaves remainder 1. So there is a prime not on the list. Contradiction. The real trick is the "+1", which guarantees a remainder of 1 against every prime on the list.
A common mistake: N itself need not be prime. With the first six primes, 2·3·5·7·11·13 + 1 = 30,031 = 59 × 509. It is not prime, but both its factors are new primes, which is all the proof needs.
To find primes, the ancient method is the sieve of Eratosthenes: write the numbers out, cross off multiples of 2, then of 3, then of 5, and so on. Whatever is never crossed off is prime. You can stop early, because every composite number up to N has a prime factor no bigger than √N. For N = 100 that means sieving only with 2, 3, 5 and 7.
Blue: still standing. Grey: crossed off (1 starts grey because it is not prime). After 2, 3, 5 and 7 are used, exactly the primes remain: there are 25 of them below 100.
How common are primes? There are 25 below 100, 168 below 1,000, 1,229 below 10,000 and 9,592 below 100,000. They thin out, but in a pattern: near N, roughly one number in ln N is prime, where ln is the natural logarithm. This is the prime number theorem, proved independently by Hadamard and de la Vallée Poussin in 1896: the count of primes up to N is about N ÷ ln N, with the ratio tending to 1 (slowly).
The count is a fresh sieve run in your browser each time. The ratio of the true count to N ÷ ln N falls slowly toward 1.
At N = 100,000, the true count is 9,592 against the estimate 8,686: a ratio of 1.104. The estimate improves, but only like 1/ln N, which is a snail's pace. The exact size of the error is what the Riemann hypothesis is about, in the last section.
Here is a fact so familiar you never question it: every whole number above 1 splits into primes in exactly one way, apart from the order. 360 = 2³ · 3² · 5, and nothing else. This is the fundamental theorem of arithmetic. Its uniqueness is what lets you treat the prime exponents as a number's coordinates, and from them read off everything: how many divisors, which numbers it shares factors with, whether it is a perfect square (all exponents even).
Suppose √2 = a/b. Then a² = 2b². Look at the exponent of the prime 2 on each side. In a² it is twice the exponent of 2 in a: an even number. In 2b² it is one more than twice the exponent in b: an odd number. A number cannot have both an even and an odd count of 2s, because the factorisation is unique. The real trick is uniqueness of the prime fingerprint; without it, the two counts could differ without contradiction.
Uniqueness is not automatic. In the number system built from √−5 (numbers a + b√−5), 6 = 2 × 3 = (1 + √−5)(1 − √−5), and all four factors are irreducible there. Unique factorisation fails. This is why nineteenth-century attempts at Fermat's Last Theorem stumbled, and why algebra (34/73) grew the idea of "ideals": to repair the lost uniqueness. Try a number yourself.
Trial division by every number up to √n. For n with exponents e₁, e₂, …, the divisor count is (e₁+1)(e₂+1)⋯, and Euler's φ(n) counts the numbers up to n sharing no factor with n.
For 360 = 2³·3²·5 the divisor count is 4 × 3 × 2 = 24, and φ(360) = 96. 999,983 is the largest prime below a million: the factoriser tries every candidate up to 999 and finds none. 1,048,576 is 2²⁰, a perfect square because the exponent is even.
It is 10 o'clock. What time is it in 5 hours? Not 15: it is 3. On a clock you add and then keep only the remainder after dividing by 12. Mathematicians write 15 ≡ 3 (mod 12) and call it congruence. You can add, subtract and multiply this way and everything still works.
The interesting question is division. When can you undo a multiplication on the clock? On a 12-hour clock, multiplying by 5 can be undone: 5 × 5 = 25 ≡ 1, so 5 is its own inverse. Multiplying by 4 cannot: 4 × 3 = 12 ≡ 0, and information is lost. The rule is exactly Euclid:
If gcd(a, n) = 1, Bézout gives integers x and y with a·x + n·y = 1. Reduce mod n: the n·y term vanishes, so a·x ≡ 1, and x is the inverse. If instead d = gcd(a, n) > 1, every multiple of a is a multiple of d, so it can never be 1 mod n. The real trick is reading Bézout's equation mod n.
This is group theory arriving without announcement: the numbers coprime to n form a group under multiplication, with φ(n) elements. Mod a prime, every nonzero number has an inverse, so clock arithmetic becomes a field. Play with the multiplication table.
Green cells: products that equal 1, so the two factors are inverses. Orange cells: a non-zero times a non-zero giving 0. Those can only appear when n is not prime. The ringed row is your a.
At n = 12, a = 5: the row 5·k mod 12 for k = 0 to 11 hits 1 at k = 5, so 5 is its own inverse; there are φ(12) = 4 invertible numbers (1, 5, 7, 11) and plenty of orange cells. Switch to n = 13 and every nonzero row hits 1 exactly once, and there are no orange cells.
Fermat noticed in the 1600s that if p is prime and a is not a multiple of p, then raising a to the power p − 1 always lands on 1 mod p.
Take the numbers 1, 2, …, p − 1 and multiply each by a, mod p. The results are all different (a has an inverse, so no two collide) and none is 0, so you get the same list in a different order. Multiply all of both lists together: ap−1·(p − 1)! ≡ (p − 1)!. The real trick is that multiplying by an invertible element only permutes the list. Cancel the (p − 1)! (also invertible) and what remains is ap−1 ≡ 1.
Euler generalised it to any modulus n: aφ(n) ≡ 1 when gcd(a, n) = 1. That is Lagrange's theorem from group theory in costume. RSA, published in 1977 by Rivest, Shamir and Adleman, turns it into a lock. Pick two primes p and q and publish n = p·q. Choose a public exponent e coprime with φ(n) = (p − 1)(q − 1). Anyone can encrypt a message m as me mod n. Only someone who knows p and q can compute φ(n), and so the inverse d with e·d ≡ 1 mod φ(n), and decrypt by cd mod n. It works because med = m1 + kφ(n) = m · (mφ(n))k ≡ m by Euler.
Play with a toy lock. The primes here are tiny, so an attacker can factor n in a flash; real keys use primes hundreds of digits long.
Computed with exact big-integer arithmetic. e is the smallest odd number from 3 up that is coprime with φ(n); d comes from the extended Euclidean algorithm. The attacker's cost is the number of odd trial divisions before the smaller prime is found.
With p = 19 and q = 41, n = 779, φ = 720 and the first valid e is 7, giving d = 103. The message 42 encrypts to 42⁷ mod 779 = 329, and 329 to the power 103 mod 779 gives 42 back. Finding the smaller prime by trial division takes only 9 tries. A 2,048-bit modulus, a typical size for RSA keys today, has 617 decimal digits. At that size, trial division would need around 10³⁰⁰ steps, and the best factoring methods, which are far cleverer, are still hopelessly out of reach for a well-chosen 2,048-bit key. No one has proved factoring is hard; only that nobody has found a fast method on ordinary computers. (Shor's 1994 quantum algorithm would factor quickly on a large, error-corrected quantum computer, which does not exist yet.)
Number theory is full of questions a ten-year-old can read and the best mathematicians cannot answer. Here is the status of the famous ones.
| Problem | Says | Status |
|---|---|---|
| Goldbach (1742) | Every even number above 2 is a sum of two primes | Open. Checked by computer up to 4 × 10¹⁸ (2013, published 2014) |
| Twin primes | Infinitely many pairs p, p + 2 | Open. In 2013 Zhang proved infinitely many pairs within 70 million of each other; a collaborative project cut that to 246 |
| Riemann hypothesis (1859) | The zeros of the zeta function lie on one line, which pins down how primes are spread | Open. A Clay Millennium Problem with a US$1 million prize (2000) |
| Fermat's Last Theorem | No whole-number solutions to xⁿ + yⁿ = zⁿ for n > 2 | Proved: Wiles announced in 1993, a gap was repaired with Richard Taylor in 1994, published 1995 |
Goldbach is easy to watch. For each even number n, count the ways to write it as a sum of two primes. The count does not go to zero, and in fact tends to grow, though ragged: a famous "comet" shape.
Each dot is one even number: how many ways it splits into two primes. The orange dot is your n. Seeing it hold for n up to 2,000 proves nothing; the theorem is about all of them.
For n = 100 there are 6 ways (3 + 97, 11 + 89, 17 + 83, 29 + 71, 41 + 59, 47 + 53). For n = 4 and n = 6 there is exactly 1, the smallest the count ever gets; for n = 2,000 there are 37. The lower edge of the comet rises, which is why Goldbach is believed true. Believing is not proving.
The Riemann hypothesis connects back to the prime-counting estimate above. The zeta function ζ(s) = 1 + 1/2s + 1/3s + … is secretly a statement about primes, because unique factorisation turns the sum into a product over primes. Its complex zeros control how far the true count of primes strays from N ÷ ln N. The hypothesis says the error is as small as it can be.
Whole numbers have a hidden skeleton of primes, and Euclid's algorithm lets you reach in and use it without ever factoring. Clock arithmetic turns divisibility into group theory, and the gap between multiplying and factoring locks your messages. Meanwhile some of the simplest-sounding questions remain open after centuries.
Try this: this week, take the number on a clock, a bus, a date or a price tag and factor it in your head. Spot which is divisible by 3 by adding its digits (why does that work mod 3?). Notice how often you reach for the fingerprint.
Sources. The theorems are standard (Hardy & Wright; Rosen; Ireland & Rosen). The prime number theorem (Hadamard and de la Vallée Poussin, 1896) is standard history. Goldbach checked to 4 × 10¹⁸: Oliveira e Silva, Herzog and Pardi, Mathematics of Computation 83 (2014). Bounded gaps: Zhang (2013; Annals 2014), Polymath8 reduced the bound to 246, per the project's retrospective on arXiv. Wiles: announced 1993, repaired with Taylor and published in Annals of Mathematics 1995. Largest known prime: 2^136,279,841 − 1, 41,024,320 digits, GIMPS, October 2024; no later record found in a search made for this piece. Course contents: MIT OCW 18.781 page. All numbers shown were computed in node: gcd(1071, 462) = 21 = 1071·(−3) + 462·7; π(100) = 25, π(1000) = 168, π(10⁴) = 1,229, π(10⁵) = 9,592; 2·3·5·7·11·13 + 1 = 30,031 = 59 × 509; φ(360) = 96; RSA with p = 19, q = 41: n = 779, e = 7, d = 103, 42 encrypts to 329 and decrypts to 42; Goldbach counts g(100) = 6, g(2000) = 37; 2,048 bits = 617 digits.